/**
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 *
 * 你可以按 任何顺序 返回答案。
 *
 *题解：https://leetcode.cn/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/
 * 剪枝分析：事实上，如果 n = 7, k = 4，从 5 开始搜索就已经没有意义了，这是因为：即使把 5 选上，后面的数只有 6 和 7，一共就 3 个候选数，凑不出 4 个数的组合。因此，搜索起点有上界，这个上界是多少，可以举几个例子分析。
 *例如：n = 6 ，k = 4。
 *
 * path.size() == 1 的时候，接下来要选择 3 个数，搜索起点最大是 4，最后一个被选的组合是 [4, 5, 6]；
 * path.size() == 2 的时候，接下来要选择 2 个数，搜索起点最大是 5，最后一个被选的组合是 [5, 6]；
 * path.size() == 3 的时候，接下来要选择 1 个数，搜索起点最大是 6，最后一个被选的组合是 [6]；
 *
 * 再如：n = 15 ，k = 4。
 * path.size() == 1 的时候，接下来要选择 3 个数，搜索起点最大是 13，最后一个被选的是 [13, 14, 15]；
 * path.size() == 2 的时候，接下来要选择 2 个数，搜索起点最大是 14，最后一个被选的是 [14, 15]；
 * path.size() == 3 的时候，接下来要选择 1 个数，搜索起点最大是 15，最后一个被选的是 [15]；
 * 可以归纳出：
 * 搜索起点的上界 + 接下来要选择的元素个数 - 1 = n
 * 其中，接下来要选择的元素个数 = k - path.size()，整理得到：
 * 搜索起点的上界 = n - (k - path.size()) + 1
 * 所以，我们的剪枝过程就是：把 i <= n 改成 i <= n - (k - path.size()) + 1
 *
 *
 */
class Combine {
    List<List<Integer>> ret=new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        Deque<Integer> qu=new LinkedList<>();
        dfs(1,n,k,0,qu);
        return ret;
    }
    public void dfs(int begin,int n,int k,int count,Deque<Integer> qu){
        if(count==k){
            ret.add(new ArrayList<>(qu));
            return;
        }
        for(int i=begin;i<=n-(k-qu.size())+1;i++){
            qu.addLast(i);
              dfs(i+1,n,k,count+1,qu);
              qu.removeLast();
        }
    }
}